/*
 * 0048. 主元素 III
 * 给定一个整型数组，找到主元素，它在数组中的出现次数严格大于数组元素个数的1/k。
 * https://www.lintcode.com/problem/majority-number-iii/description
 * 
 * 样例
 * 给出数组 [3,1,2,3,2,3,3,4,4,4] ，和 k = 3，返回 3
 * 
 * 挑战
 * 要求时间复杂度为O(n)，空间复杂度为O(k)
 *  
 * 2018.06.23 @jeyming
 */
package majority_number_iii_0048;

import java.util.Collections;
import java.util.List;

public class Majority_number_iii_0048 {
	/**
     * @param nums: A list of integers
     * @param k: An integer
     * @return: The majority number
     */
    public int majorityNumber(List<Integer> nums, int k) {
        // write your code here
        Collections.sort(nums);
		int numsCnt = nums.size() * 1/k;
		int cnt = 1;
		int tmp = nums.get(0);
		for(int i = 1; i < nums.size(); ++i) {
			if(tmp == nums.get(i)) {
				++cnt;
			} else {
				cnt = 1;
				tmp = nums.get(i);
			}
			if(cnt > numsCnt) {
				return tmp;
			} 
		}
		return 0;
    }

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
